package io.github.hadyang.leetcode;

import java.util.LinkedList;

/**
 * @author haoyang.shi
 * @date 2020-01-02
 */
public class TreeNodeCodec {

  // Encodes a tree to a single string.
  public static String serialize(TreeNode root) {
    StringBuilder res = new StringBuilder("[");
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.offerLast(root);

    while (!queue.isEmpty()) {
      TreeNode node = queue.pollFirst();
      if (node == null) {
        res.append("null,");
        continue;
      }
      queue.offerLast(node.left);
      queue.offerLast(node.right);

      res.append(node.val).append(",");
    }

    res.setCharAt(res.length() - 1, ']');

    return res.toString();
  }

  // Decodes your encoded data to tree.
  public static TreeNode deserialize(String data) {
    if (data == null) return null;
    data = data.replaceAll("\\[", "").replaceAll("]", "");
    String[] strs = data.split(",");
    if (strs.length == 0) return null;
    if (strs[0].length() == 0) return null;
    if (strs[0].equals("null")) return null;

    TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.offerLast(root);

    int i = 1;
    while (!queue.isEmpty()) {
      TreeNode node = queue.pollFirst();

      if (i >= strs.length) {
        break;
      }

      if (!strs[i].equals("null")) {
        node.left = new TreeNode(Integer.parseInt(strs[i]));
        queue.offerLast(node.left);
      }
      i++;

      if (i >= strs.length) {
        break;
      }

      if (!strs[i].equals("null")) {
        node.right = new TreeNode(Integer.parseInt(strs[i]));
        queue.offerLast(node.right);
      }
      i++;
    }

    return root;
  }
}
